﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions
{
    /*
     * It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?

     * */
    class Problem77 : IProblem
    {
        int limit = 71;

        public string Calculate()
        {
            int count = CountCombinations(limit, limit);

            return count.ToString();
        }

        public int CountCombinations(int n, int max)
        {
            if (n == 2 && max >= 2)
                return 1;
            if (n == 3 && max >= 3)
                return 1;

            int count = 0;
            for (int i = (n <= max ? n : max); i > 1; i--)
            {
                if (!CommonFunctions.IsPrime(i))
                    continue;

                int remaining = n - i;

                if (remaining > 0)
                    count += CountCombinations(remaining, i);
                else
                    count++;
            }
            return count;
        }
    }
}
